WannaflyCamp day2

Posted on | In ,

达成成就：和qls、MjLee合影
FDU温老师 数论函数选讲

数论函数

整除分块

  • 形式：$\sum_{i=1}^{i=n} ⌊\frac{n}{i}⌋$
  • 这个式子只有$\sqrt{n}$种取值
  • 每个相同值的块，最后一个数 $i$ 是$n/(n/i)$，故可以$\sqrt{n}$处理出上面式子的结果
1
2
3
4
for(int l=1,r;l<=n;i=r+1){
    r=n/(n/l);
    ans += (r-l+1)*(n/l);
}

一些定义和性质

  • $\lceil \frac{n}{ab} \lceil$ = $\lceil\frac{\lceil\frac{n}{a}\rceil}{b} \rceil$，$\lfloor \frac{n}{ab} \rfloor$ = $\lfloor\frac{\lfloor \frac{n}{a} \rfloor }{b} \rfloor$
  • $\lfloor \frac{n}{i}\rfloor$只有$\sqrt{n}$中取值

莫比乌斯

莫比乌斯函数

定义

莫比乌斯函数 $\mu(n)$ ，设$n=p_1^{k1}·p_2^{k2}·····p_m^{km}$，则有：
$$
\mu(n)=
\left{\begin{matrix}
1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n=1\
(-1)^m \ \ \ \ \ \ \prod _{i=1}^{i=m}k_i \
0 \ \ \ {\rm otherwise}(k_i>1)
\end{matrix}\right.
$$

性质
  • 莫比乌斯函数是积性函数，即$\mu(a·b)=\mu(a)·\mu(b)，(\gcd(a,b)=1)$
  • 根据上面性质，我们可以采取线性筛法，用 O(n)O(n) 的时间预处理出所有 $[1, n]$ 内的莫比乌斯函数值。
  • $\sum_{d|n}{\mu(d)}=[n=1]$，即只有当且仅当n=1时，上式子才为1，反之为0。
  • $\sum_{d|n}{\frac{\mu(d)}{d}}=\frac {\phi (n)}{n}$

莫比乌斯反演

公式

如果 f(n), g(n) 是数论函数，且满足：

A

题意

题解

B

题意

题解

C

题意

题解

D

题意

题解

E

题意

题解

F

题意

题解

G

题意

题解

H

题意

题解

I

题意

题解

J

题意

题解

K

再见

L

题解

处理出n个圆和两条边的距离后跑最短路即可

NWERC2015 Debugging

题解

  • 二分的$\log$次的
  • 定义f(n)：n行代码debug的代价
  • 转移：$ f(n)=f(\lceil n/(i+1) \rceil ) + r + i·p$
  • 转移的时候整除分块即可
  • 时间复杂度O(n)，实际上不到O(n)，因为$\lceil \frac{n}{ab} \rceil$ = $\lceil\frac{\frac{n}{a}}{b} \rceil$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e6+100;
const ll INF = 1e18+2;

ll n, r, minx, p, dp[maxn];

ll dfs(ll n)
{
    if(n<=1) return dp[n]=0;
    if(dp[n]!=INF) return dp[n];
    dp[n]=(n-1)*p+r;
    for(int l=1,rr;l<n;l=rr+1)
    {
        rr=n/(n/l);
        dp[n]=min(dp[n], dfs((n+(n/l))/(n/l + 1)) + r + (n/l) *p);
    }
    return dp[n];
}「

int main()
{
    scanf("%lld%lld%lld", &n, &r, &p);
    for(int i=1;i<=n;i++)
    dp[i]=INF;
    dfs(n);
    printf("%lld\n", dp[n]);
}